

public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        MinTopPile mergeKLists = new MinTopPile(lists.length);
        for(ListNode node : lists) {
            if(node != null) {
                mergeKLists.offer(node);
            }

        }
        ListNode list = new ListNode(-1,null);
        ListNode t = list;
        while( !mergeKLists.isEmpty() ) {

            ListNode min = mergeKLists.poll();
            if(min != null) {
                t.next = min;
                t = min;
                if(min.next != null) {
                    mergeKLists.offer(min.next);

                }

            }
        }
        return list.next;

    }
}
class MinTopPile {

    private ListNode[] arr;
    private int size;

    public MinTopPile(int capacity) {
        arr = new ListNode[capacity];
    }

    public boolean offer(ListNode node) {
        if (isFull()) {
            return false;
        }
        int i = size++;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].val > node.val) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = node;

        return true;
    }


    public ListNode poll() {
        if (isEmpty()) {
            return null;
        }
        //先交换
        swap(0,size - 1);
        size--;
        ListNode ret = arr[size];
        arr[size] = null;
        //下潜
        down(0);
        return ret;
    }
    private void swap(int i, int j) {
        ListNode t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min = i;
        if (left < size && arr[min].val > arr[left].val ) {
            min = left;
        }
        if (right < size && arr[min].val > arr[right].val) {
            min = right;
        }
        if (min != i) {
            swap(i,min);
            down(min);
        }
    }


    public boolean isEmpty() {
        return size == 0;
    }


    public boolean isFull() {
        return size == arr.length;
    }

}
